#pragma once

#include <cmath>
#include <vector>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        for (int i = 0; i < (int)nums.size();) {
            if (nums.at(i) <= 0) {
                nums.at(i) = nums.back();
                nums.pop_back();
            } else {
                ++i;
            }
        }

        for (auto& num : nums) {
            auto i = std::abs(num);
            if (i >= 1 && i <= (int)nums.size())
                nums.at(i - 1) = -std::abs(nums.at(i - 1));
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (nums.at(i) > 0)
                return i + 1;
        }
        return nums.size() + 1;
    }
};
